#define  _CRT_SECURE_NO_WARNINGS 1
#include"tree.h"


BTNode* BuyBTNode(char x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->Data = x;
	node->left = node->right = NULL;

	return node;
}


BTNode* BinaryTreeCreate()
{
	BTNode* nodeA = BuyBTNode('A');
	BTNode* nodeB = BuyBTNode('B');
	BTNode* nodeC = BuyBTNode('C');
	BTNode* nodeD = BuyBTNode('D');
	BTNode* nodeE = BuyBTNode('E');
	BTNode* nodeF = BuyBTNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

//前序遍历 根左右
void preOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->Data);
	preOrder(root->left);
	preOrder(root->right);
}
//中序遍历 左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	preOrder(root->left);
	printf("%c ", root->Data);
	preOrder(root->right);
}
//后续遍历 左右根
void postOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%c ", root->Data);
}
//求二叉树节点的个数
//int BinaryTreeSize(BTNode* root,int size)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	size++;
//	BinaryTreeSize(root->left, size);
//	BinaryTreeSize(root->right, size);
//
//	return size;
//}

//void BinaryTreeSize(BTNode* root, int* size)
//{
//	if (root == NULL)
//	{
//		return ;
//	}
//	(*size)++;
//	BinaryTreeSize(root->left, size);
//	BinaryTreeSize(root->right, size);
//}
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{

		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;

	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeSize(root->right);
}

//二叉树第k层节点的个数
int BinaryTreeKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeKSize(root->left, k - 1) + BinaryTreeKSize(root->right, k - 1);

}

//二叉树的深度，高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdep = BinaryTreeDepth(root->left);
	int rightdep = BinaryTreeDepth(root->right);

	return 1 + (leftdep > rightdep ? leftdep : rightdep);
}


//二叉树查找节点为x
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->Data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}

}


//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BinaryTreeDestroy(&((*root)->left));
	BinaryTreeDestroy(&((*root)->right));

	free(*root);

	*root = NULL;

}


//层序遍历
void levelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", top->Data);
		if (top->left)
		{
			QueuePush(&q,top->left);
		}
		if (top->right)
		{
			QueuePush(&q,top->right);
		}
		
	}
	QueueDestroy(&q);
}

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root) 
{
	Queue q;
	QueueInit(&q);
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//两种情况，
	// 1）队列里全为空就是完全二叉树
  	// 2) 队列里存在数据就是非完全二叉树

	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}

	}

	QueueDestry(&q);
	return true;



}



